Quantum Circuit
   HOME

TheInfoList



OR:

In
quantum information theory Quantum information is the information of the quantum state, state of a quantum system. It is the basic entity of study in quantum information theory, and can be manipulated using quantum information processing techniques. Quantum information re ...
, a quantum circuit is a
model A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure. Models c ...
for
quantum computation Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
, similar to classical circuits, in which a computation is a sequence of
quantum gate In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, lik ...
s,
measurements Measurement is the quantification of attributes of an object or event, which can be used to compare with other objects or events. In other words, measurement is a process of determining how large or small a physical quantity is as compared t ...
, initializations of
qubit In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
s to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known as
DiVincenzo's criteria The DiVincenzo criteria are conditions necessary for constructing a quantum computer, conditions proposed in 2000 by the theoretical physicist David P. DiVincenzo, as being those necessary to construct such a computer—a computer first proposed b ...
. Circuits are written such that the horizontal axis is time, starting at the left hand side and ending at the right. Horizontal lines are
qubit In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
s, doubled lines represent classical
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
s. The items that are connected by these lines are operations performed on the qubits, such as measurements or gates. These lines define the sequence of events, and are usually not physical cables. The graphical depiction of quantum circuit elements is described using a variant of the
Penrose graphical notation In mathematics and physics, Penrose graphical notation or tensor diagram notation is a (usually handwritten) visual depiction of multilinear functions or tensors proposed by Roger Penrose in 1971. A diagram in the notation consists of several sha ...
.
Richard Feynman Richard Phillips Feynman (; May 11, 1918 – February 15, 1988) was an American theoretical physicist, known for his work in the path integral formulation of quantum mechanics, the theory of quantum electrodynamics, the physics of the superflu ...
used an early version of the quantum circuit notation in 1986.


Reversible classical logic gates

Most elementary
logic gate A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate, ...
s of a classical computer are not reversible. Thus, for instance, for an
AND gate The AND gate is a basic digital logic gate that implements logical conjunction (∧) from mathematical logic AND gate behaves according to the truth table. A HIGH output (1) results only if all the inputs to the AND gate are HIGH (1). If not all ...
one cannot always recover the two input bits from the output bit; for example, if the output bit is 0, we cannot tell from this whether the input bits are 01 or 10 or 00. However, reversible gates in classical computers are easily constructed for bit strings of any length; moreover, these are actually of practical interest, since irreversible gates must always increase physical
entropy Entropy is a scientific concept, as well as a measurable physical property, that is most commonly associated with a state of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynam ...
. A reversible gate is a reversible function on ''n''-bit data that returns ''n''-bit data, where an ''n''-bit data is a string of bits ''x''1,''x''2, ...,''x''''n'' of length ''n''. The set of ''n''-bit data is the space ''n'', which consists of 2''n'' strings of 0's and 1's. More precisely: an ''n''-bit reversible gate is a
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
mapping ''f'' from the set ''n'' of ''n''-bit data onto itself. An example of such a reversible gate ''f'' is a mapping that applies a fixed permutation to its inputs. For reasons of practical engineering, one typically studies gates only for small values of ''n'', e.g. ''n''=1, ''n''=2 or ''n''=3. These gates can be easily described by tables.


Quantum logic gates

The quantum logic gates are reversible
unitary transformation In mathematics, a unitary transformation is a transformation that preserves the inner product: the inner product of two vectors before the transformation is equal to their inner product after the transformation. Formal definition More precisely, ...
s on at least one qubit. Multiple qubits taken together are referred to as
quantum register In quantum computing, a quantum register is a system comprising multiple qubits. It is the quantum analogue of the classical processor register. Quantum computers perform calculations by manipulating qubits within a quantum register. Definition ...
s. To define quantum gates, we first need to specify the quantum replacement of an ''n''-bit datum. The ''quantized version'' of classical ''n''-bit space ''n'' is the
Hilbert space In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
:H_= \ell^2(\^n). This is by definition the space of complex-valued functions on ''n'' and is naturally an
inner product space In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often den ...
. \ell^2 means the function is a
square-integrable function In mathematics, a square-integrable function, also called a quadratically integrable function or L^2 function or square-summable function, is a real- or complex-valued measurable function for which the integral of the square of the absolute value i ...
. This space can also be regarded as consisting of linear combinations, or superpositions, of classical bit strings. Note that ''H''QB(''n'') is a vector space over the complex numbers of
dimension In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
2''n''. The elements of this
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
are the possible state-vectors of ''n''-
qubit In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
quantum register In quantum computing, a quantum register is a system comprising multiple qubits. It is the quantum analogue of the classical processor register. Quantum computers perform calculations by manipulating qubits within a quantum register. Definition ...
s. Using Dirac ket notation, if ''x''1,''x''2, ...,''x''''n'' is a classical bit string, then : , x_1, x_2, \cdots,x_n \rangle \quad is a special ''n''-qubit register corresponding to the function which maps this classical bit string to 1 and maps all other bit strings to 0; these 2''n'' special ''n''-qubit registers are called ''computational basis states''. All ''n''-qubit registers are complex linear combinations of these computational basis states. Quantum logic gates, in contrast to classical logic gates, are always reversible. One requires a special kind of reversible function, namely a
unitary Unitary may refer to: Mathematics * Unitary divisor * Unitary element * Unitary group * Unitary matrix * Unitary morphism * Unitary operator * Unitary transformation * Unitary representation * Unitarity (physics) * ''E''-unitary inverse semigrou ...
mapping, that is, a linear transformation of a complex
inner product space In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often den ...
that preserves the
Hermitian inner product In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often de ...
. An ''n''-qubit (reversible) quantum gate is a unitary mapping ''U'' from the space ''H''QB(''n'') of ''n''-qubit registers onto itself. Typically, we are only interested in gates for small values of ''n''. A reversible ''n''-bit classical logic gate gives rise to a reversible ''n''-bit quantum gate as follows: to each reversible ''n''-bit logic gate ''f'' corresponds a quantum gate ''W''''f'' defined as follows: : W_f( , x_1, x_2, \cdots,x_n \rangle) = , f(x_1, x_2, \cdots, x_n) \rangle. Note that ''W''''f'' permutes the computational basis states. Of particular importance is the controlled NOT gate (also called
CNOT In computer science, the controlled NOT gate (also C-NOT or CNOT), controlled-''X'' gate'','' controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-base ...
gate) ''W''CNOT defined on a quantized 2 qubit. Other examples of quantum logic gates derived from classical ones are the
Toffoli gate In logic circuits, the Toffoli gate (also CCNOT gate), invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It is also known as the "controlle ...
and the
Fredkin gate The Fredkin gate (also CSWAP gate and conservative logic gate) is a computational circuit suitable for reversible computing, invented by Edward Fredkin. It is ''universal'', which means that any logical or arithmetic operation can be constructed en ...
. However, the Hilbert-space structure of the qubits permits many quantum gates that are not induced by classical ones. For example, a relative phase shift is a 1 qubit gate given by multiplication by the phase shift operator: : P(\varphi) =\begin 1 & 0 \\ 0 & e^ \end, so : P(\varphi), 0 \rangle = , 0 \rangle \quad P(\varphi), 1 \rangle = e^, 1 \rangle.


Reversible logic circuits

Again, we consider first ''reversible'' classical computation. Conceptually, there is no difference between a reversible ''n''-bit circuit and a reversible ''n''-bit logic gate: either one is just an invertible function on the space of ''n'' bit data. However, as mentioned in the previous section, for engineering reasons we would like to have a small number of simple reversible gates, that can be put together to assemble any reversible circuit. To explain this assembly process, suppose we have a reversible ''n''-bit gate ''f'' and a reversible ''m''-bit gate ''g''. Putting them together means producing a new circuit by connecting some set of ''k'' outputs of ''f'' to some set of ''k'' inputs of ''g'' as in the figure below. In that figure, ''n''=5, ''k''=3 and ''m''=7. The resulting circuit is also reversible and operates on ''n''+''m''−''k'' bits. We will refer to this scheme as a ''classical assemblage'' (This concept corresponds to a technical definition in Kitaev's pioneering paper cited below). In composing these reversible machines, it is important to ensure that the intermediate machines are also reversible. This condition assures that ''intermediate'' "garbage" is not created (the net physical effect would be to increase entropy, which is one of the motivations for going through this exercise). Note that each horizontal line on the above picture represents either 0 or 1, not these probabilities. Since quantum computations are reversible, at each 'step' the number of lines must be the same number of input lines. Also, each input combination must be mapped to a single combination at each 'step'. This means that each intermediate combination in a quantum circuit is a bijective function of the input. Now it is possible to show that the
Toffoli gate In logic circuits, the Toffoli gate (also CCNOT gate), invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It is also known as the "controlle ...
is a universal gate. This means that given any reversible classical ''n''-bit circuit ''h'', we can construct a classical assemblage of Toffoli gates in the above manner to produce an (''n''+''m'')-bit circuit ''f'' such that : f(x_1, \ldots, x_n, \underbrace) = (y_1, \ldots, y_n, \underbrace) where there are ''m'' underbraced zeroed inputs and :(y_1, \ldots, y_n) = h(x_1, \ldots, x_n). Notice that the end result always has a string of ''m'' zeros as the ancilla bits. No "rubbish" is ever produced, and so this computation is indeed one that, in a physical sense, generates no entropy. This issue is carefully discussed in Kitaev's article. More generally, any function ''f'' (bijective or not) can be simulated by a circuit of Toffoli gates. Obviously, if the mapping fails to be
injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
, at some point in the simulation (for example as the last step) some "garbage" has to be produced. For quantum circuits a similar composition of qubit gates can be defined. That is, associated to any ''classical assemblage'' as above, we can produce a reversible quantum circuit when in place of ''f'' we have an ''n''-qubit gate ''U'' and in place of ''g'' we have an ''m''-qubit gate ''W''. See illustration below: The fact that connecting gates this way gives rise to a unitary mapping on ''n''+''m''−''k'' qubit space is easy to check. In a real quantum computer the physical connection between the gates is a major engineering challenge, since it is one of the places where
decoherence Quantum decoherence is the loss of quantum coherence. In quantum mechanics, particles such as electrons are described by a wave function, a mathematical representation of the quantum state of a system; a probabilistic interpretation of the wa ...
may occur. There are also universality theorems for certain sets of well-known gates; such a universality theorem exists, for instance, for the pair consisting of the single qubit phase gate ''U''θ mentioned above (for a suitable value of θ), together with the 2-qubit CNOT gate ''W''CNOT. However, the universality theorem for the quantum case is somewhat weaker than the one for the classical case; it asserts only that any reversible ''n''-qubit circuit can be ''approximated'' arbitrarily well by circuits assembled from these two elementary gates. Note that there are
uncountably In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many Element (mathematics), elements to be countable set, countable. The uncountability of a set is closely related to its cardinal number: a se ...
many possible single qubit phase gates, one for every possible angle θ, so they cannot all be represented by a finite circuit constructed from .


Quantum computations

So far we have not shown how quantum circuits are used to perform computations. Since many important numerical problems reduce to computing a unitary transformation ''U'' on a finite-dimensional space (the celebrated
discrete Fourier transform In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex- ...
being a prime example), one might expect that some quantum circuit could be designed to carry out the transformation ''U''. In principle, one needs only to prepare an ''n'' qubit state ψ as an appropriate superposition of computational basis states for the input and measure the output ''U''ψ. Unfortunately, there are two problems with this: * One cannot measure the phase of ψ at any computational basis state so there is no way of reading out the complete answer. This is in the nature of
measurement in quantum mechanics In quantum physics, a measurement is the testing or manipulation of a physical system to yield a numerical result. The predictions that quantum physics makes are in general probabilistic. The mathematical tools for making predictions about what m ...
. * There is no way to efficiently prepare the input state ψ. This does not prevent quantum circuits for the discrete Fourier transform from being used as intermediate steps in other quantum circuits, but the use is more subtle. In fact quantum computations are ''probabilistic''. We now provide a mathematical model for how quantum circuits can simulate ''probabilistic'' but classical computations. Consider an ''r''-qubit circuit ''U'' with register space ''H''QB(''r''). ''U'' is thus a unitary map :H_ \rightarrow H_. In order to associate this circuit to a classical mapping on bitstrings, we specify * An ''input register'' ''X'' = ''m'' of ''m'' (classical) bits. * An ''output register'' ''Y'' = ''n'' of ''n'' (classical) bits. The contents ''x'' = ''x''1, ..., ''x''''m'' of the classical input register are used to initialize the qubit register in some way. Ideally, this would be done with the computational basis state : , \vec,0\rangle= , x_1, x_2, \cdots, x_, \underbrace \rangle, where there are ''r''-''m'' underbraced zeroed inputs. Nevertheless, this perfect initialization is completely unrealistic. Let us assume therefore that the initialization is a mixed state given by some density operator ''S'' which is near the idealized input in some appropriate metric, e.g. : \operatorname\left(\big, , \vec,0\rangle \langle \vec,0 , - S\big, \right) \leq \delta. Similarly, the output register space is related to the qubit register, by a ''Y'' valued observable ''A''. Note that observables in quantum mechanics are usually defined in terms of ''projection valued measures'' on R; if the variable happens to be discrete, the projection valued measure reduces to a family indexed on some parameter λ ranging over a countable set. Similarly, a ''Y'' valued observable, can be associated with a family of pairwise orthogonal projections indexed by elements of ''Y''. such that : I = \sum_ \operatorname_y. Given a mixed state ''S'', there corresponds a probability measure on ''Y'' given by : \operatorname\ = \operatorname(S \operatorname_y ). The function ''F'':''X'' → ''Y'' is computed by a circuit ''U'':''H''QB(''r'') → ''H''QB(''r'') to within ε if and only if for all bitstrings ''x'' of length ''m'' :\left\langle \vec,0 \big, U^* \operatorname_ U \big, \vec,0 \right\rangle = \left\langle \operatorname_ U( , \vec,0\rangle) \big, U( , \vec,0\rangle) \right\rangle \geq 1 - \epsilon. Now : \left, \operatorname (S U^* \operatorname_ U) - \left\langle \vec,0 \big, U^* \operatorname_ U \big, \vec,0 \right\rangle\\leq \operatorname (\big, , \vec,0\rangle \langle \vec,0 , - S\big, ) \, U^* \operatorname_ U \, \leq \delta so that :\operatorname (S U^* \operatorname_ U) \geq 1 - \epsilon - \delta. Theorem. If ε + δ < 1/2, then the probability distribution : \operatorname\ = \operatorname (S U^* \operatorname_ U) on ''Y'' can be used to determine ''F''(''x'') with an arbitrarily small probability of error by majority sampling, for a sufficiently large sample size. Specifically, take ''k'' independent samples from the probability distribution Pr on ''Y'' and choose a value on which more than half of the samples agree. The probability that the value ''F''(''x'') is sampled more than ''k''/2 times is at least : 1 - e^, where γ = 1/2 - ε - δ. This follows by applying the
Chernoff bound In probability theory, the Chernoff bound gives exponentially decreasing bounds on tail distributions of sums of independent random variables. Despite being named after Herman Chernoff, the author of the paper it first appeared in, the result is d ...
.


See also

* Abstract index notation *
Angular momentum diagrams (quantum mechanics) In quantum mechanics and its applications to quantum many-particle systems, notably quantum chemistry, angular momentum diagrams, or more accurately from a mathematical viewpoint angular momentum graphs, are a diagrammatic method for representing ...
*
Circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
and BQP *
Matrix product state Matrix product state (MPS) is a quantum state of many particles (in N sites), written in the following form: : , \Psi\rangle = \sum_ \operatorname\left _1^ A_2^ \cdots A_N^\right, s_1 s_2 \ldots s_N\rangle, where A_i^ are complex, square matr ...
uses
Penrose graphical notation In mathematics and physics, Penrose graphical notation or tensor diagram notation is a (usually handwritten) visual depiction of multilinear functions or tensors proposed by Roger Penrose in 1971. A diagram in the notation consists of several sha ...
*
Quantum register In quantum computing, a quantum register is a system comprising multiple qubits. It is the quantum analogue of the classical processor register. Quantum computers perform calculations by manipulating qubits within a quantum register. Definition ...
*
Spin network In physics, a spin network is a type of diagram which can be used to represent states and interactions between particles and fields in quantum mechanics. From a mathematical perspective, the diagrams are a concise way to represent multilinear f ...
s *
Trace diagram In mathematics, trace diagrams are a graphical means of performing computations in linear and multilinear algebra. They can be represented as (slightly modified) graphs in which some edges are labeled by matrices. The simplest trace diagrams r ...


References

*. *. *. *. *.


External links


Q-circuit
is a macro package for drawing quantum circuit diagrams in LaTeX.
Quantum Circuit Simulator (Davy Wybiral)
a browser-based quantum circuit diagram editor and simulator.
Quantum Computing Playground
a browser-based quantum scripting environment.
Quirk - Quantum Circuit Toy
a browser-based quantum circuit diagram editor and simulator. {{emerging technologies, quantum=yes, other=yes Quantum information science Models of computation